# LeetCode 739、每日温度
# 一、题目描述
根据每日 气温 列表，请重新生成一个列表，对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。
例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。
# 二、题目解析
这道题目最 “难” 的一个点是题目的理解。
给定列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，为啥输出就是 [1, 1, 4, 2, 1, 1, 0, 0] ？
下面来一个个进行解释。
对于输入 73，它需要 经过一天 才能等到温度的升高，也就是在第二天的时候，温度升高到 74 ，所以对应的结果是 1。
对于输入 74，它需要 经过一天 才能等到温度的升高，也就是在第三天的时候，温度升高到 75 ，所以对应的结果是 1。
对于输入 75，它经过 1 天后发现温度是 71，没有超过它，继续等，一直 等了四天，在第七天才等到温度的升高，温度升高到 76 ，所以对应的结果是 4 。
对于输入 71，它经过 1 天后发现温度是 69，没有超过它，继续等，一直 等了两天，在第六天才等到温度的升高，温度升高到 72 ，所以对应的结果是 2 。
对于输入 69，它 经过一天 后发现温度是 72，已经超过它，所以对应的结果是 1 。
对于输入 72，它 经过一天 后发现温度是 76，已经超过它，所以对应的结果是 1 。
对于输入 76，后续 没有温度 可以超过它，所以对应的结果是 0 。
对于输入 73，后续 没有温度 可以超过它，所以对应的结果是 0 。
也就是说，这道题目就是给你一个值，让你找到右边第一个比它大的数，它们两则的下标差就是输出结果。
好了，理解了题意我们来思考如何求解：借助单独递增栈来处理。
具体操作如下：
遍历整个数组，如果栈不空，且当前数字大于栈顶元素，那么如果直接入栈的话就不是 递增栈 ，所以需要取出栈顶元素，由于当前数字大于栈顶元素的数字，而且一定是第一个大于栈顶元素的数，直接求出下标差就是二者的距离。
继续看新的栈顶元素，直到当前数字小于等于栈顶元素停止，再将数字入栈，这样就可以一直保持递增栈，且每个数字和第一个大于它的数的距离也可以算出来。
# 三、参考代码
# 1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 每日温度（ LeetCode 739 ）：https://leetcode-cn.com/problems/daily-temperatures
class Solution {
/**
* 维护一个单调递增栈，栈内元素从栈底到栈顶依次减小
* 入栈的元素要和当前栈内栈首元素进行比较
* 如果大于栈首元素，说明温度比之前更高，那么它们的下标差就是栈首元素等了多少天等到的更高温度的结果
* 如果小于栈首元素，说明温度比之前更低，说明还没有等到更高的温度，直接放入到栈中
*/
public static int[] dailyTemperatures(int[] temperatures) {
// 构建一个栈,用来存放每日温度的下标
Stack<Integer> stack = new Stack<>();
// 构建一个数组，用来保存输出结果
int[] res = new int[temperatures.length];
// 从头开始遍历每天的温度
for (int i = 0; i < temperatures.length; i++) {
// 拿到当天的温度，需要和栈首元素进行比较
// 如果此时栈不为空并且当天的温度大于栈首元素
while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
// 首先获取栈首元素的值，并将元素从栈中移除
int preIndex = stack.pop();
// 它们的下标差就是栈首元素等了多少天等到的更高温度的结果，保存到输出数组 res 中
res[preIndex] = i - preIndex;
}
// 再把当天的温度的下标值存放到栈中
stack.push(i);
}
// 最后输出 res 数组即可
return res;
}
}
# **2、**C++ 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 每日温度（ LeetCode 739 ）：https://leetcode-cn.com/problems/daily-temperatures
/**
* 维护一个单调递增栈，栈内元素从栈底到栈顶依次减小
* 入栈的元素要和当前栈内栈首元素进行比较
* 如果大于栈首元素，说明温度比之前更高，那么它们的下标差就是栈首元素等了多少天等到的更高温度的结果
* 如果小于栈首元素，说明温度比之前更低，说明还没有等到更高的温度，直接放入到栈中
*/
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& T) {
// 构建一个栈,用来存放每日温度的下标
stack<int> stk;
// 构建一个数组，用来保存输出结果
vector<int> res(T.size());
// 从头开始遍历每天的温度
for (int i = 0; i < T.size(); i++) {
// 拿到当天的温度，需要和栈首元素进行比较
// 如果此时栈不为空并且当天的温度大于栈首元素
while (!stk.empty() && T[i] > T[stk.top()]) {
// 首先获取栈首元素的值，并将元素从栈中移除
int preIndex = stk.top();
stk.pop();
// 它们的下标差就是栈首元素等了多少天等到的更高温度的结果，保存到输出数组 res 中
res[preIndex] = i - preIndex;
}
// 再把当天的温度的下标值存放到栈中
stk.push(i);
}
// 最后输出 res 数组即可
return res;
}
};
# 3、Python 代码
# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 每日温度（ LeetCode 739 ）：https://leetcode-cn.com/problems/daily-temperatures
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
# 构建一个栈,用来存放每日温度的下标
stack = []
# 获取数组长度
length = len(temperatures)
# 构建一个数组，用来保存输出结果
res = [0] * length
# 从头开始遍历每天的温度
for i in range(length):
# 拿到当天的温度，不断的和栈顶元素进行比较
temperature = temperatures[i]
# 如果栈顶元素存在并且当天的温度大于栈顶元素
# 意味着栈顶元素等到了第一个温度比它更高的那一天
# 它们的下标差就是栈顶元素等了多少天等到的更高温度的结果
while stack and temperature > temperatures[stack[-1]]:
# 首先获取栈顶元素的值，也就是每日温度的下标值
preIndex = stack.pop()
# 它们的下标差就是栈顶元素等了多少天等到的更高温度的结果，保存到输出数组 res 中
res[preIndex] = i - preIndex
# 再把当天的温度的下标值存放到栈中
# 注意：是下标索引值
stack.append(i)
# 最后输出 res 数组即可
return res
# 四、复杂度分析
时间复杂度：O(n)，其中 n 是温度列表的长度。正向遍历温度列表一遍，对于温度列表中的每个下标，最多有一次进栈和出栈的操作。
空间复杂度：O(n)，其中 n 是温度列表的长度。需要维护一个单调栈存储温度列表中的下标。